#ifndef RAYCAST_H
#define RAYCAST_H

#include <vector>
#include <raylib.h>
#include <raymath.h>
#include <algorithm>
#include <optional>
#include <stack>

class RayCast
{
public:
    std::vector<std::pair<Vector2, Vector2>> walls;
    struct PointWallVector
    {
        Vector2 point;
        Vector2 wall_1;
        Vector2 wall_2;
    };
    std::vector<PointWallVector*> pointWallVector;
    PointWallVector* last_wall_point;
    PointWallVector* curr_wall_point;
    std::vector<std::pair<Vector2, float>> basePoints;
    std::vector<Vector2> polygonPoints;
    float defaultDistance = 200;
    struct Intersection
    {
        Vector2 point;
        float distance;
        bool onEnd;
        Intersection* next;
        Intersection* head;
    };
    Intersection* curr_inter;
    Intersection* last_inter;
    std::vector<Intersection*> usefulIntersection;
    std::vector<Intersection*> usfulTmp;
    std::vector<Intersection> intersections_;

    RayCast() {}

    void cast(const Vector2& center)
    {
        
        polygonPoints.clear();
        polygonPoints.push_back(center);
        // 投射光线
        castRay(center);
        // 给usefulIntersection排序
        sortPointsByAngle(center);
        // 组合多边形
        if(IsKeyPressed(KEY_SPACE))
            std::cout << std::endl;

        // while(usefulIntersection.at(0)->next!=nullptr) vectorRotateLeft(usefulIntersection,1);
        for(auto& inter : usefulIntersection)
        {
            curr_inter = inter;
            // 清理这个点的链表中的无关点
            if(curr_inter->next!=nullptr)
            {   
                for(auto& p : pointWallVector)
                {
                    if(Vector2Equals(p->point,curr_inter->point) && curr_inter->next!=nullptr)
                    if(
                        Vector2DotProduct(Vector2Subtract(p->wall_1,p->point),Vector2Subtract(curr_inter->next->point,p->point))*
                        Vector2DotProduct(Vector2Subtract(p->wall_2,p->point),Vector2Subtract(curr_inter->next->point,p->point))
                        > 0
                    ) 
                    // 删除下一个节点
                    {
                        delete curr_inter->next;
                        curr_inter->next = nullptr;
                    }
                    
                }
            }
            // 如果没有子节点
            // 直接添加到多边形队列
            if(inter->next==nullptr)
                polygonPoints.push_back(inter->point);
            // 如果有子节点
            else
            {
                // 检查上一个点与这个点是否公用一条边
                bool eq;
                if(last_wall_point==nullptr){
                    PointWallVector* temp = getPointWall(curr_inter);
                    eq = (isOnSegment(temp->point, temp->wall_1, last_inter->point) || isOnSegment(temp->point, temp->wall_2, last_inter->point));
                } 
                else eq = Vector2Equals(last_wall_point->wall_1, curr_inter->point) || Vector2Equals(last_wall_point->wall_2, curr_inter->point);
                if(eq)
                // 如果公用一条边，按顺序添加到多边形队列
                {
                    while(curr_inter->next!=nullptr)
                    {
                        polygonPoints.push_back(curr_inter->point);
                        // if(curr_inter!=inter) delete curr_inter;
                        curr_inter = curr_inter->next;
                    }
                    polygonPoints.push_back(curr_inter->point);
                }
                else// 如果不共用同一条边，反向添加到多边形队列
                {
                    curr_inter = [&]()->Intersection*{
                        Intersection* prev = nullptr;
                        Intersection* curr = curr_inter;
                        while (curr != nullptr) {
                            Intersection* nextTemp = curr->next;
                            curr->next = prev;
                            prev = curr;
                            curr = nextTemp;
                        }
                        return prev;
                    }();
                    while(curr_inter->next!=nullptr)
                    {
                        polygonPoints.push_back(curr_inter->point);
                        // if(curr_inter!=inter) delete curr_inter;
                        curr_inter = curr_inter->next;
                    }
                    polygonPoints.push_back(curr_inter->point);
                }
                
            }
            
            last_inter = curr_inter;
            last_wall_point = getPointWall(last_inter);
            
        }
        if(polygonPoints.size() > 2)
        {
            Vector2 sec = polygonPoints[1];
            polygonPoints.push_back(sec);
        }
        // 清理数据
        // for(auto& i : usefulIntersection) delete i;
        // usefulIntersection.clear();
    }

    void vectorRotateLeft(std::vector<Intersection*>& vec, int k) {
        if (vec.empty()) return;
        k = k % vec.size();
        if (k == 0) return;
        std::rotate(vec.begin(), vec.begin() + k, vec.end());
    }

    void sortPointsByAngle(const Vector2& center) {
        std::sort(usefulIntersection.begin(), usefulIntersection.end(), [&center](const Intersection* a, const Intersection* b) {
            float angleA = atan2f(a->point.y - center.y, a->point.x - center.x);
            float angleB = atan2f(b->point.y - center.y, b->point.x - center.x);
            return angleA > angleB;
        });
    }

    void castRay(const Vector2& rayStart)
    {
        for(auto& basePoint : basePoints)
        {
            bool crossEnd = false;
            intersections_.clear();
            for(int i=0; i<walls.size(); i++)
            {
                // 找到交点
                auto intersection = findRaySegmentIntersection(rayStart, basePoint.first, walls[i].first, walls[i].second);
                // 添加交点和距离
                if(intersection.has_value())
                {
                    // 判断是否在端点上
                    bool onEnd = false;
                    if(Vector2Equals(intersection.value(),walls[i].first) || Vector2Equals(intersection.value(),walls[i].second))
                    {
                        crossEnd = true;
                        onEnd = true;
                    }
                    if(![&]()->bool{for(auto& inter : intersections_) if(Vector2Equals(inter.point,intersection.value())) return true; return false;}())
                    intersections_.push_back(Intersection{intersection.value(),Vector2Distance(rayStart,intersection.value()),onEnd,nullptr,nullptr});
                }
            }
            // 判断是否有交点
            if(intersections_.empty()) continue;
            // 判断是否经过端点
            if(!crossEnd) continue;
            // 按距离排序<升序?>
            std::sort(intersections_.begin(), intersections_.end(), 
                [](const auto& a, const auto& b) { return a.distance < b.distance; });
            if(!intersections_.at(0).onEnd) continue;
            // 添加到useful
            Intersection* c = nullptr;
            for(auto cur=intersections_.begin(); cur!=intersections_.end(); cur++)
            {
                Intersection* is = new Intersection(cur->point,cur->distance,cur->onEnd,nullptr,nullptr);
                if(c!=nullptr) c->next = is;
                    else usefulIntersection.push_back(is);
                c = is;
                if(cur->onEnd==false) break;
            }
            // for(auto cur=usefulIntersection.begin()+1; cur!=usefulIntersection.end(); cur++) (*cur-1)->next = (*cur);
            
        }
    }

    PointWallVector* getPointWall(Intersection* p){
        for(auto& wv : pointWallVector)
            if(Vector2Equals(wv->point,p->point))return wv;
        return nullptr;
    }

    bool isOnSegment(const Vector2& v1, const Vector2& v2, const Vector2& point, float epsilon = 1e-5f) {
        // 叉积 判断共线性
        float cross = (point.x - v1.x) * (v2.y - v1.y) - (point.y - v1.y) * (v2.x - v1.x);
        if (std::abs(cross) > epsilon) {
            return false;
        }
        // 点积 判断点是否在线段之间
        float dot = (point.x - v1.x) * (v2.x - v1.x) + (point.y - v1.y) * (v2.y - v1.y);
        float segmentLengthSquared = (v2.x - v1.x) * (v2.x - v1.x) + 
                                    (v2.y - v1.y) * (v2.y - v1.y);
        
        return (dot >= -epsilon && dot <= segmentLengthSquared + epsilon);
    }

    // 线段交点
    std::optional<Vector2> findRaySegmentIntersection(
        const Vector2& rayStart,
        const Vector2& rayPoint,
        const Vector2& segStart,
        const Vector2& segEnd
    ) {
        Vector2 rayDir = Vector2Subtract(rayPoint,rayStart);
        Vector2 segVec = Vector2Subtract(segEnd,segStart);
        Vector2 startVec = Vector2Subtract(segStart,rayStart);
        
        float cross = crossProduct(rayDir, segVec);
        
        if (std::abs(cross) < 1e-6) {
            return std::nullopt;
        }
        
        float t = crossProduct(startVec, segVec) / cross;
        float u = crossProduct(startVec, rayDir) / cross;
        
        if (t >= 0 && u >= 0 && u <= 1) {
            Vector2 intersection = {
                rayStart.x + rayDir.x * t,
                rayStart.y + rayDir.y * t
            };
            return intersection;
        }
        
        return std::nullopt;
    }

    // 计算叉积
    float crossProduct(const Vector2& a, const Vector2& b) {
        return a.x * b.y - a.y * b.x;
    }
    
    void setWalls(std::vector<std::pair<Vector2, Vector2>> o_walls)
    {
        walls = o_walls;
        for(auto& wall : walls)
        {
            basePoints.push_back({wall.first, defaultDistance});
            basePoints.push_back({wall.second, defaultDistance});
        }

        bool merge;
        do {
            merge = false;
            for(auto wall = basePoints.begin(); wall != basePoints.end(); ++wall) {
                for(auto w = std::next(wall); w != basePoints.end(); ) {
                    if(Vector2Equals(w->first, wall->first)) {
                        w = basePoints.erase(w);
                        merge = true;
                        break;
                    } else {
                        ++w;
                    }
                }
                if(merge) break; // 如果删除了元素，重新开始外层循环
            }
        } while(merge);
        
        // 添加墙向量
        for(auto& point : basePoints)
        {
            Vector2 wall1{0,0};
            Vector2 wall2{0,0};
            PointWallVector* p = new PointWallVector(point.first, {0,0}, {0,0});
            for(auto& wall : walls)
            {
                if(Vector2Equals(wall.first, point.first))
                {
                    if(Vector2Equals(wall1,{0,0})) wall1 = wall.second;
                    else if(Vector2Equals(wall2,{0,0})) wall2 = wall.second;
                }else 
                if(Vector2Equals(wall.second, point.first))
                {
                    if(Vector2Equals(wall1,{0,0})) wall1 = wall.first;
                    else if(Vector2Equals(wall2,{0,0})) wall2 = wall.first;
                }
            }
            p->wall_1 = wall1;
            p->wall_2 = wall2;
            pointWallVector.push_back(p);
        }
    }
};

#endif